import java.util.Comparator;
import java.util.PriorityQueue;

//创建一个类，其应用Comparator接口并且实现比较的相反逻辑
class IntReverseCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        //比较的相反逻辑
        return o2.compareTo(o1);
    }
}

class Solution {
    public int[] smallestK(int[] arr, int k) {
        //设定返回值
        int[]ret=new int[k];
        //k为0则直接返回
        if(k==0){
            return ret;
        }
        //Priority默认创建小根堆，因此使用应用了Comparator接口并且完成比较反逻辑的对象构造堆可以创建出大根堆
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(new IntReverseCmp());
        //将前k个元素放入堆中
        for(int i=0;i<k;i++){
            maxHeap.offer(arr[i]);
        }
        //遍历其余N-k个元素
        for(int i=k;i<arr.length;i++){
            int val=maxHeap.peek();
            //判断其余元素是否比堆顶（队头）元素(堆中的最大元素),若小于则说明该元素可以放入堆中
            if(arr[i]<val){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        //将堆中元素放入返回的数组中
        for(int i=0;i<k;i++){
            ret[i]=maxHeap.poll();
        }
        return ret;
    }
}